package com.wang.sort2;

import java.util.LinkedList;
/**
 * @Author: along
 * @Create: 2021/4/20
 * @Description:判断是否为完全二叉树
 */
public class Demo19_CompleteBTree {

        public static class Node {
            public int value;
            public Node left;
            public Node right;

            public Node(int value) {
                this.value = value;
            }
        }
        //广度优先遍历
        public static boolean isCBT1(Node head) {
            if (head == null) {
                return true;
            }
            LinkedList<Node> queue = new LinkedList<>();
            // 是否遇到过左右两个孩子不双全的节点
            boolean leaf = false;
            Node l = null;
            Node r = null;
            queue.add(head);
            while (!queue.isEmpty()) {
                head = queue.poll();
                l = head.left;
                r = head.right;
                if ((leaf && !(l == null && r == null)) || (l == null && r != null)) {
                    return false;
                }
                if (l != null) {
                    queue.add(l);
                }
                if (r != null) {
                    queue.add(r);
                }
                if (l == null || r == null) {
                    leaf = true;
                }
            }
            return true;
        }
        //递归
        public static boolean isCBT2(Node head) {
            if (head == null) {
                return true;
            }
            return process(head).isCBT;
        }
        //包装返回信息
        public static class Info {
            public boolean isFull;//子树是否满
            public boolean isCBT;//子树是否为完全二叉树
            public int height;//树高

            public Info(boolean full, boolean cbt, int h) {
                isFull = full;
                isCBT = cbt;
                height = h;
            }
        }

        public static Info process(Node head) {
            //空树也可视作完全二叉树
            if (head == null) {
                return new Info(true, true, 0);
            }
            Info leftInfo = process(head.left);
            Info rightInfo = process(head.right);
            int height = Math.max(leftInfo.height, rightInfo.height) + 1;
            boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
            boolean isCBT = false;
            //四种情况
            //1）满二叉树也是一颗完全二叉树
            //2）左子树为完全二叉树，右子树为满二叉树且左子树比右子树高度大1
            //3）左子树为满二叉树，右子树为完全二叉树且左子树比右子树高度大1
            //4）左子树为满二叉树，右子树为完全二叉树且左右子树高度相等
            if (isFull) {
                isCBT = true;
            } else {
                if (leftInfo.isCBT && rightInfo.isCBT) {
                    if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
                        isCBT = true;
                    }
                    if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
                        isCBT = true;
                    }
                    if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
                        isCBT = true;
                    }
                }
            }
            return new Info(isFull, isCBT, height);
        }

        // for test
        public static Node generateRandomBST(int maxLevel, int maxValue) {
            return generate(1, maxLevel, maxValue);
        }

        // for test
        public static Node generate(int level, int maxLevel, int maxValue) {
            if (level > maxLevel || Math.random() < 0.5) {
                return null;
            }
            Node head = new Node((int) (Math.random() * maxValue));
            head.left = generate(level + 1, maxLevel, maxValue);
            head.right = generate(level + 1, maxLevel, maxValue);
            return head;
        }

        public static void main(String[] args) {
            int maxLevel = 5;
            int maxValue = 100;
            int testTimes = 1000000;
            for (int i = 0; i < testTimes; i++) {
                Node head = generateRandomBST(maxLevel, maxValue);
                if (isCBT1(head) != isCBT2(head)) {
                    System.out.println("Oops!");
                }
            }
            System.out.println("finish!");
        }

}
